home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1994 November: Tool Chest / Dev.CD Nov 94.toast / New System Software Extensions / OpenDoc A6 / OpenDoc Parts Framework / OPF / Found / BCCollec / Tools / Search / BCSearcV.cpp < prev    next >
Encoding:
Text File  |  1994-04-21  |  4.0 KB  |  136 lines  |  [TEXT/MPS ]
  1. //  The C++ Booch Components (Version 2.1)
  2. //  (C) Copyright 1990-1993 Grady Booch. All Rights Reserved.
  3. //
  4. //  Restricted Rights Legend
  5. //  Use, duplication, or disclosure is subject to restrictions as set forth 
  6. //  in subdivision (c)(1)(ii) of the Rights in Technical Data and Computer 
  7. //  Software clause at DFARS 252.227-7013. 
  8. //
  9. //  BCSearcV.cpp
  10. //
  11. //  This file contains the definitions for the vector searching tools.
  12.  
  13. #include "BCSearcV.h"
  14.  
  15. template<class Item, class Sequence>
  16. BC_TSearch<Item, Sequence>::BC_TSearch()
  17.   : fIsEqual(0) {}
  18.   
  19. template<class Item, class Sequence>
  20. BC_TSearch<Item, Sequence>::
  21.   BC_TSearch(BC_Boolean (*IsEqual)(const Item& x, const Item& y))
  22.     : fIsEqual(IsEqual) {}
  23.   
  24. template<class Item, class Sequence>
  25. BC_TSearch<Item, Sequence>::~BC_TSearch() {}
  26.   
  27. template<class Item, class Sequence>
  28. void BC_TSearch<Item, Sequence>::
  29.   SetIsEqualFunction(BC_Boolean (*IsEqual)(const Item& x, const Item& y))
  30. {
  31.   fIsEqual = IsEqual;
  32. }
  33.  
  34. template<class Item, class Sequence>
  35. BC_TSequentialSearch<Item, Sequence>::BC_TSequentialSearch() {}
  36.  
  37. template<class Item, class Sequence>
  38. BC_TSequentialSearch<Item, Sequence>::
  39.   BC_TSequentialSearch(BC_Boolean (*IsEqual)(const Item& x, const Item& y))
  40.     : BC_TSearch<Item, Sequence>(IsEqual) {}
  41.     
  42. template<class Item, class Sequence>
  43. BC_TSequentialSearch<Item, Sequence>::~BC_TSequentialSearch() {}
  44.   
  45. template<class Item, class Sequence>
  46. BC_ExtendedIndex BC_TSequentialSearch<Item, Sequence>::
  47.   Location(const Sequence& target, const Item& key, BC_Index start)
  48. {
  49.   for (BC_Index index = start; (index < target.Length()); index++)
  50.     if (fIsEqual(target[index], key))
  51.       return index;
  52.   return -1;
  53. }
  54.  
  55. template<class Item, class Sequence>
  56. BC_TOrderedSearch<Item, Sequence>::BC_TOrderedSearch()
  57.   : fIsLessThan(0) {}
  58.  
  59. template<class Item, class Sequence>
  60. BC_TOrderedSearch<Item, Sequence>::
  61.   BC_TOrderedSearch(BC_Boolean (*IsEqual)(const Item& x, const Item& y),
  62.                     BC_Boolean (*IsLessThan)(const Item& x, const Item& y))
  63.     : BC_TSearch<Item, Sequence>(IsEqual),
  64.       fIsLessThan(IsLessThan) {}
  65.     
  66. template<class Item, class Sequence>
  67. BC_TOrderedSearch<Item, Sequence>::~BC_TOrderedSearch() {}
  68.   
  69. template<class Item, class Sequence>
  70. void BC_TOrderedSearch<Item, Sequence>::
  71.   SetIsLessThanFunction(BC_Boolean (*IsLessThan)(const Item& x, const Item& y))
  72. {
  73.   fIsLessThan = IsLessThan;
  74. }
  75.  
  76. template<class Item, class Sequence>
  77. BC_ExtendedIndex BC_TOrderedSearch<Item, Sequence>::
  78.   Location(const Sequence& target, const Item& key, BC_Index start)
  79. {
  80.   for (BC_Index index = start; (index < target.Length()); index++) {
  81.     if (fIsEqual(target[index], key))
  82.       return index;
  83.     if (fIsLessThan(key, target[index]))
  84.       return -1;
  85.   }
  86.   return -1;
  87. }
  88.  
  89. template<class Item, class Sequence>
  90. BC_TBinarySearch<Item, Sequence>::BC_TBinarySearch()
  91.   : fIsLessThan(0) {}
  92.  
  93. template<class Item, class Sequence>
  94. BC_TBinarySearch<Item, Sequence>::
  95.   BC_TBinarySearch(BC_Boolean (*IsEqual)(const Item& x, const Item& y),
  96.                    BC_Boolean (*IsLessThan)(const Item& x, const Item& y))
  97.     : BC_TSearch<Item, Sequence>(IsEqual),
  98.       fIsLessThan(IsLessThan) {}
  99.     
  100. template<class Item, class Sequence>
  101. BC_TBinarySearch<Item, Sequence>::~BC_TBinarySearch() {}
  102.   
  103. template<class Item, class Sequence>
  104. void BC_TBinarySearch<Item, Sequence>::
  105.   SetIsLessThanFunction(BC_Boolean (*IsLessThan)(const Item& x, const Item& y))
  106. {
  107.   fIsLessThan = IsLessThan;
  108. }
  109.  
  110. template<class Item, class Sequence>
  111. BC_ExtendedIndex BC_TBinarySearch<Item, Sequence>::
  112.   Location(const Sequence& target, const Item& key, BC_Index start)
  113. {
  114.   BC_Index lower = start;
  115.   BC_Index upper = target.Length();
  116.   if (!upper)
  117.     return -1;
  118.   else
  119.     --upper;
  120.   while (lower <= upper) {
  121.     BC_Index index = (lower + upper) / 2;
  122.     if (fIsEqual(target[index], key))
  123.       return index;
  124.     if (fIsLessThan(key, target[index])) {
  125.       if (!index)
  126.         return -1;
  127.       upper = index - 1;
  128.     } else {
  129.       if (index == (target.Length() - 1))
  130.         return -1;
  131.       lower = index + 1;
  132.     }
  133.   }
  134.   return -1;
  135. }
  136.